package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/17 17:45
 * todo: 让字符串成为回文串的最少插入次数
 */
public class LeetCode_1312 {
    /**
     * 这道题依然可以用范围尝试模型来做
     * 来分析下它的所有可能性 [L...R]
     *      1、以L开始，不以R结尾,然后将R位置的元素插入到L左边
     *          dp[L][R] = dp[L][R-1]+1
     *      2、不以L开始，以R结尾，然后将L位置的元素插入到R右边
     *          dp[L][R] = dp[L+1][R]+1
     *      3、前提：【L】 == 【R】 以L开始，以R结尾
     *          dp[L][R] = dp[L+1][R-1]
     */
    public int minInsertions(String s) {
        if (s == null || s.length() <= 1 || (s.length() == 2 && s.charAt(0) == s.charAt(1))){
            return 0;
        }
        char []str = s.toCharArray();
        int dp[][] = new int[str.length][str.length];
        //先填基本数据
        for (int i=0;i<dp.length;i++){
            dp[i][i] = 0;
            if (i != dp.length-1){
                dp[i][i+1] = str[i]==str[i+1]?0:1;
            }
        }
        //再填普遍数据
        for (int i = dp.length-3;i>=0;i--){
            for (int j=i+2;j<dp[i].length;j++){
                dp[i][j] = Math.min(dp[i+1][j],dp[i][j-1])+1;
                if (str[i] == str[j]){
                    dp[i][j] = Math.min(dp[i+1][j-1],dp[i][j]);
                }
            }
        }
        return dp[0][str.length-1];
    }

    public static void main(String[] args) {
        LeetCode_1312 demo = new LeetCode_1312();
        String s = "mbadm";
        System.out.println(demo.minInsertions(s));
    }
}
